package xio.ccf_201612;

import java.util.Scanner;

/**
 * 压缩编码 201612-4 100分
 * 参考：http://www.voidcn.com/article/p-yficcnnf-bmq.html
 * Created by ywb47 on 2017/10/9.
 */
public class CodeCompression {
    public static void main(String[] args) {
        int n;

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        int v[] = new int[n + 1];
        int sum[] = new int[n + 1];
        long dp[][] = new long[n + 1][n + 1];
        int p[][] = new int[n + 1][n + 1];

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][j] = -1; //初始化为-1，表示未曾访问
            }
        }
        sum[0] = 0;
        // 输入
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();

            sum[i] = sum[i - 1] + v[i];
            dp[i][i] = 0;
            p[i][i] = i;
        }

        // DP计算
        for (int len = 2; len <= n; len++)
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;

                for (int k = p[i][j - 1]; k <= p[i + 1][j] && k+1<= j; k++) {  //四边形不等式优化
                    long val = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]; //sum[j] - sum[i-1] 即本次移动这两堆石子 需要移动的数量
                    if (dp[i][j] == -1 || dp[i][j] > val) {
                        dp[i][j] = val;
                        p[i][j] = k;
                    }
                }
            }

        // 输出结果
        System.out.println(dp[1][n]);

        sc.close();
    }
}
